package com.leetcode.leetcode2;

/**
 * 最大正方形
 *
 * @author luhd
 * @date 2023-07-28
 */
public class Practice221 {

    /**
     * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
     * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
     * 输出：4
     */
    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        // int[][] matrix = {{1,0,1,0,0},{1,0,1,1,1},{1,1,1,1,1},{1,0,0,1,0}};
        System.out.println(maximalSquare(matrix));
    }

    public static int maximalSquare(char[][] matrix) {
        if (matrix.length<1||matrix[0].length<1) {
            return 0;
        }
        int height = matrix.length;
        int width = matrix[0].length;
        int maxArea = 0;
        int[][] dp = new int[height+1][width+1];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j]-'0';
                }else if (matrix[i][j]-'0' == 1){
                    dp[i][j] = Math.min(Math.min(matrix[i-1][j-1]-'0',matrix[i-1][j]-'0'),matrix[i][j-1]-'0') +1;
                }
                maxArea = Math.max(maxArea,dp[i][j]*dp[i][j]);
            }
        }
        return maxArea;
    }
}